package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 翻转等价二叉树951.java
 * @Description https://leetcode-cn.com/problems/flip-equivalent-binary-trees/
 * 我们可以为二叉树 T 定义一个 翻转操作 ，如下所示：选择任意节点，然后交换它的左子树和右子树。
 *
 * 只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。
 *
 * 这些树由根节点 root1 和 root2 给出。如果两个二叉树是否是翻转 等价 的函数，则返回 true ，否则返回 false 
 *
 * @createTime 2021年08月05日 19:21:00
 */
public class 翻转等价二叉树951 {
	public boolean flipEquiv(TreeNode root1, TreeNode root2) {
		if (root1 == root2) {
			return true;
		}
		if (root1 == null || root2 == null || root1.val != root2.val) {
			return false;
		}
		//可能是本来就相等，还有一种可能是需要翻转之后才相等
		return (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left))
				|| (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right));
	}
}
